package expressiontree;

import java.util.Stack;

import tokens.CellToken;
import tokens.LiteralToken;
import tokens.OperatorToken;
import tokens.Token;

/**
 * An expression tree created from a Stack.
 * 
 * @author James Santos-Calacat
 *
 */
public class ExpressionTree {
	
	/**
	 * The root.
	 */
	private ExpressionTreeNode root;
	
	/**
	 * Constructs an expression tree with a single node, the root.
	 * @param the_root_item The token to be put into the root.
	 */
	public ExpressionTree (final Token the_root_item)
	{
		root = new ExpressionTreeNode(the_root_item, null, null);
	}
	
	/**
	 * Gives the illusion of making the tree empty.
	 */
	public void makeEmpty()
	{
		root = null;
	}
	
	/**
	 * Returns the root of the tree.
	 * @return What is your root?
	 */
	public ExpressionTreeNode getRoot()
	{
		return root;
	}
	
	/**
	 * Builds the expression tree given the stack.
	 * @param the_stack The stack.
	 */
	public void BuildExpressionTree(Stack<Token> the_stack)
	{
		root = GetExpressionTree(the_stack);
		
		// handle empty stack
		if (!the_stack.isEmpty())
		{
			System.out.println("Error in BuildExpressionTree.");
		}
	}
	
	/**
	 * Recursive method to build an expression tree given a stack.
	 * @param the_stack The stack.
	 * @return What is the root of the tree you are creating?
	 */
	public static ExpressionTreeNode GetExpressionTree(Stack<Token> the_stack) { 
	    ExpressionTreeNode returnTree; 
	    Token token = null; 
	 
	    if (the_stack.isEmpty()) 
	        return null; 
	    
	    // if underflow occurs, then there is nothing in the stack
	    // if there is something to be popped
	    if (the_stack.peek() != null)
	    {
	    	// pop!
	    	token = (Token) the_stack.pop();  // need to handle stack underflow 
	    }
	    
	    // if the token popped is a literal or a cell token
	    if ((token instanceof LiteralToken) || 
	        (token instanceof CellToken) ) { 
	 
	        // Literals and Cells are leaves in the expression tree  
	        returnTree = new ExpressionTreeNode(token, null, null);  
	        return returnTree;  
	        
	    } else if (token instanceof OperatorToken) { // if it is an operator
	        // Continue finding tokens that will form the 
	        // right subtree and left subtree.   
	        ExpressionTreeNode rightSubtree = GetExpressionTree (the_stack);  
	        ExpressionTreeNode leftSubtree  = GetExpressionTree (the_stack);  
	        returnTree = 
	           new ExpressionTreeNode(token, leftSubtree, rightSubtree); 
	        return returnTree; 
	    } else {
	    	// you get here if the token is invalid
	    	return null;
	    }
	}  
}
